// https://soj.turingedu.cn/problem/60203/
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
int rad(); // read int
const int max_size = 5 + 100;
const int maxn = 5 + 1e5;

int n, mod;
int a[maxn];
ll sum[maxn << 2];
struct Tag {
    ll add, mul;
} tag[maxn << 2];

inline void merge(int now) {
    sum[now] = (sum[now << 1] + sum[now << 1 | 1]) % mod;
}
inline void update_node(int now, int l, int r, ll add = 0, ll mul = 1) {
    sum[now] = (sum[now] * mul % mod + add * (r - l + 1) % mod) % mod;
    tag[now].add = (tag[now].add * mul + add) % mod;
    tag[now].mul = (tag[now].mul * mul) % mod;
}

inline void push_down(int now, int l, int r) {
    if (tag[now].add == 0 && tag[now].mul == 1) return;
    int mid = l + r >> 1;
    update_node(now << 1, l, mid, tag[now].add, tag[now].mul);
    update_node(now << 1 | 1, mid + 1, r, tag[now].add, tag[now].mul);
    tag[now].add = 0, tag[now].mul = 1;
}

void init(int now, int l, int r) {
    tag[now].add = 0, tag[now].mul = 1;
    if (l == r) {
        sum[now] = a[l] % mod;
        return;
    }
    int mid = l + r >> 1;
    init(now << 1, l, mid);
    init(now << 1 | 1, mid + 1, r);
    merge(now);
}

void update(int now, int l, int r, int s, int t, ll add, ll mul) {
    if (s <= l && r <= t) {
        update_node(now, l, r, add, mul);
        return;
    }
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (s <= mid) update(now << 1, l, mid, s, t, add, mul);
    if (t > mid) update(now << 1 | 1, mid + 1, r, s, t, add, mul);
    merge(now);
}

ll ask(int now, int l, int r, int s, int t) {
    if (s <= l && r <= t) return sum[now] % mod;
    push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask(now << 1, l, mid, s, t) % mod;
    if (s > mid) return ask(now << 1 | 1, mid + 1, r, s, t) % mod;
    return (ask(now << 1, l, mid, s, t) + ask(now << 1 | 1, mid + 1, r, s, t)) % mod;
}

int main() {
    n = rad(), mod = rad();
    rf(i, n) a[i] = rad();
    init(1, 1, n);
    int q = rad();
    rf(j, q) {
        int op = rad(), s = rad(), t = rad();
        if (op == 1) {
            update(1, 1, n, s, t, 0, rad());
        } else if (op == 2) {
            update(1, 1, n, s, t, rad(), 1);
        } else if (op == 3) {
            printf("%lld\n", ask(1, 1, n, s, t));
        }
    }
}

int rad() {
    int back = 0, ch = 0, neg = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        neg = ch == '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return (back ^ -neg) + neg;
}